package com.zjw.core.algorithm;


import java.util.*;

public class TopKAlgorithm {

    public static void main(String[] args) {
        int[] num = new int[100];
        for (int i = 0; i < 100; i++) {
            num[i] = (int) (Math.random()* 500);
           // System.out.println(num[i] + " ");
        }


        Long startTime = System.currentTimeMillis();
        List<Integer> topList =  solutionByHeap(num,10);
        Long endTime = System.currentTimeMillis();
//        topList.forEach(p->{
//            System.out.println("最大的十个数:"+p);
//        });
        System.out.println("耗时:"+ (endTime - startTime)+"毫秒");


    }

    //优先队列PriorityQueue保证堆顶的第一个值是堆里最小的，后面的数依次与最小值比较，大于则替换堆里最小元素的值
    public static List<Integer> solutionByHeap(int[] input, int k) {
        List<Integer> list = new ArrayList<>();
        if (k > input.length || k == 0) {
            return list;
        }
        Queue<Integer> queue = new PriorityQueue<>();
        for (int num : input) {
            if (queue.size() < k) {
                queue.add(num);//循环数组，将前十个数放入堆，堆顶为堆得最小值
            } else if (queue.peek() < num){
                queue.poll();//数组的值大于堆顶的值，去掉堆顶的值
                queue.add(num);//将数组的值放入堆，并再次计算最小值放入堆顶
            }
        }
        while (k-- > 0) {
            list.add(queue.poll());
        }
        return list;
    }

}
